Search

Introduction

Search problem definition

We have a State Space(set) which contains all the possible states of the environment.

We have a Successor function that maps actions to their cost.

We also have a Start state and a Goal state.

State Space Graph

A mathematical representation of a search problem.

In this graph:

  • Nodes == world states
  • Edges == successors
  • Each state is unique
  • The goal is a set of goal nodes
  • Sometimes edges are one-way

  • Root node == start state
  • Children nodes == successors
  • Nodes == plans(set of actions)

For tree search problems we have:

  • A frontier: which is the set of nodes that we can potentially expand to.
  • A strategy, which is the rule that makes us choose which nodes to expand from the frontier.
  • The goal state.
Pseudo-Algorithm


The algorithm is ... if ...:

  • Complete: if it is guaranteed to find a solution.
  • Optimal: if it is guaranteed to find the least cost path.

Then we also have:

  • Time complexity: is the amount of nodes that we need to traverse.
  • Space complexity: is the amount of nodes that we need to keep in memory.

Time/Space Complexity variables

In order to continue, we need to define some variables:

  • b: maximum branching factor of search tree.
  • d: depth of the shallowest goal node.
  • m: maximum length of any path in the state space

The strategy for this tree search is: Always expand shallowest node.

Performance [Exponential in Space and Time]
  • Is it complete? Yes, we are guaranteed to find a solution if b is finite.
  • Time complexity:
  • Space complexity: , it keeps every node in memory.
  • Is it Optimal? Yes, but only if cost = 1 for each step.

The strategy for this tree search is: Always expand deepest node.

Performance [Terrible time but Good space]
  • Is it complete? No, it fails in infinite depth or looped spaces.
  • Time complexity:
  • Space complexity: , linear space.
  • Is it optimal? No lol. We could find sub-optimal before finding optimal.

Iterative deepening?

Warning

From this point on, nodes can have different costs.

The strategy for this tree search is: Always expand to the cheapest node.

Hint

We basically order the frontier by the path cost function for each node. Then we expand on the first one.

Greedy

Expand node closest to goal according to a heuristic function.

A*

Expand node that has lower cost according to this cost function